package problem662;

import javafx.util.Pair;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

//662.二叉树的最大宽度
//https://leetcode.cn/problems/maximum-width-of-binary-tree/

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        Deque<Pair<TreeNode, Integer>> deque = new ArrayDeque<>();
        deque.addLast(new Pair<>(root, 1));
        int ret = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            int left = deque.peekFirst().getValue();
            int right = deque.peekLast().getValue();
            ret = Math.max(ret, right-left+1);
            for(int i = 0; i<size; i++) {
                Pair<TreeNode, Integer> pair = deque.pollFirst();
                TreeNode node = pair.getKey();
                int index = pair.getValue();
                if(node.left != null) deque.addLast(new Pair<>(node.left, index*2));
                if(node.right != null) deque.addLast(new Pair<>(node.right, index*2+1));
            }
        }
        return ret;
    }
}